﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuickSorting
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = { 6, 2, 4, 1, 5, 9 };
            //quick_sort(x, 0, x.Length - 1);
            QuickSort(x, 0, x.Length - 1); 
            foreach (var item in x)
            {
                Console.Write(item + ",");
            }
            Console.ReadLine();
        }

        private static void QuickSort(int[] numbers, int left, int right)
        {
            if (left < right)
            {
                int middle = numbers[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true)
                {
                    //while (numbers[++i] < middle) ;
                    do
                    {
                        i++;
                    }
                    while (numbers[i] < middle);

                    do
                    {
                        j--;
                    }
                    while (numbers[j] > middle);

                    if (i >= j)
                        break;

                    int number = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = number;
                }

                QuickSort(numbers, left, i - 1);
                QuickSort(numbers, j + 1, right);
            }
        }

        static void quickSort(int[] unSorted, int low, int high)
        {
            int location = 0;
            if (low < high)
            {
                int pivot = unSorted[low];
                while (low < high)
                {
                    while (low < high && unSorted[high] > pivot)
                    {
                        high--;
                    }
                    unSorted[low] = unSorted[high];
                    while (low < high && unSorted[low] <= pivot)
                    {
                        low++;
                    }
                    unSorted[high] = unSorted[low];
                }
                unSorted[low] = pivot;

            }
        }

        static int partition(int[] unsorted, int low, int high)
        {
            int pivot = unsorted[low];
            while (low < high)
            {
                while (low < high && unsorted[high] > pivot) high --;
                unsorted[low] = unsorted[high];
                while (low < high && unsorted[low] <= pivot) low ++;
                unsorted[high] = unsorted[low];
            }
            unsorted[low] = pivot;
            return low;
        }

        static void quick_sort(int[] unsorted, int low, int high)
        {
            int loc = 0;
            if (low < high)
            {
                loc = partition(unsorted, low, high);
                quick_sort(unsorted, low, loc - 1);
                quick_sort(unsorted, loc + 1, high);
            }
        }

    }
}
